package 动态规划专项训练.动态规划训练2;

/**132.分割回文串 II
 * @author zx
 * @create 2022-04-19 9:52
 */
public class Num132 {
    public int minCut(String s) {
        char[] arr = s.toCharArray();
        int n = arr.length;
        if(n == 0){
            return 0;
        }
        boolean[][] isPalin = new boolean[n][n];
        int i,j,t;
        for(i = 0;i < n;i++){
            for(j = i;j < n;j++){
                isPalin[i][j] = false;
            }
        }
        //生成回文串
        for(t = 0;t < n;t++){
            //奇数长度回文串
            i = j = t;// i + j 永远是偶数
            while(i >= 0 && j < n && arr[i] == arr[j]){
                isPalin[i][j] = true;
                i--;
                j++;
            }
            //偶数长度回文串
            i = t;
            j = t + 1;//i + j 永远是奇数
            while(i >= 0 && j < n && arr[i] == arr[j]){
                isPalin[i][j] = true;
                i--;
                j++;
            }
        }
        int[] f = new int[n + 1];
        f[0] = 0;
        for(i = 1;i <= n;i++){
            f[i] = Integer.MAX_VALUE;
            for(j = 0;j < i;j++){
                if(isPalin[j][i - 1]){
                    f[i] = Math.min(f[j] + 1,f[i]);
                }
            }
        }
        return f[n] - 1;
    }
}
